package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         57,
		Discription: "在升序无重叠区间数组中插入区间",
		Level:       2,
		Labels: map[string]int{
			"双指针滑动": 1,
		},
	})
}

func Insert(intervals [][]int, newInterval []int) [][]int {
	i := 0
	//找到第一个区间的end比新区间的start大的
	for i < len(intervals) && newInterval[0] > intervals[i][1] {
		i++
	}
	res := append([][]int(nil), intervals[:i]...)

	//找到第一个区间的start比新区间的end大的
	for i < len(intervals) && newInterval[1] >= intervals[i][0] {
		//合并区间
		newInterval[0] = min(newInterval[0], intervals[i][0])
		newInterval[1] = max(newInterval[1], intervals[i][1])
		i++
	}

	res = append(res, newInterval)
	if i <= len(intervals)-1 {
		res = append(res, intervals[i:]...)
	}

	return res
}